#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef int DATA_TYPE;

typedef struct linklist
{
    DATA_TYPE data;
    struct linklist *next;
    struct linklist *pre;
} linknode, *plinklist;

//--------------------------函数声明--------------------------
// 创建一个空链表
plinklist list_create();
// 获得指定位置的结点
plinklist list_get(plinklist H, int pos); // 通过pos 获得第pos个位置的结点
// 判断是否尾空链表
int empty(plinklist H);
// 遍历  双向链表
int list_show(plinklist H);
// 头插
int list_head_insert(plinklist H, DATA_TYPE value);
// 尾插
int list_tail_insert(plinklist H, DATA_TYPE value);
// 指定位置插入
int list_insert(plinklist H, DATA_TYPE value, int pos); // 将value插入到第pos结点之前
// 销毁链表
int list_free(plinklist *H);
// 删除某一个位置上的结点
int list_delete(plinklist H, int pos);
// 删除value值所在的结点
int list_delete_value(plinklist H, DATA_TYPE value);
// 修改结点数据  找到原数据  修改为新数据
int list_change_vlaue(plinklist H, DATA_TYPE oldvalue, DATA_TYPE newvalue);
// 向前遍历链表
int list_show_forward(plinklist H);
// 向后遍历链表
int list_show_back(plinklist H);

int main(int argc, char const *argv[])
{
    plinklist head = list_create();
    // 头插
    printf("头插:\n");
    list_head_insert(head, 1);
    list_head_insert(head, 2);
    list_head_insert(head, 3);
    list_head_insert(head, 4);
    list_show_back(head);

    printf("尾插\n");
    list_tail_insert(head, 5);
    list_tail_insert(head, 6);
    list_show_back(head);

    printf("从后往前遍历\n");
    list_show_forward(head);

    printf("获得指定结点的值\n");
    list_get(head,0);
    list_get(head,1);
    list_get(head,5);
    list_get(head,6);
    list_get(head,7);

    printf("指定位置插入\n");
    list_insert(head,0,0);
    list_show_back(head);
    list_insert(head,1,6);
    list_show_back(head);
    list_insert(head,9,1);
    list_show_back(head);
    list_insert(head,7,7);
    list_show_back(head);

    printf("修改指定值\n");
    list_change_vlaue(head,9,99);
    list_show_back(head);
    list_change_vlaue(head,1,11);
    list_show_back(head);
    list_change_vlaue(head,1,111);
    list_show_back(head);
    list_change_vlaue(head,0,99);
    list_show_back(head);

 //   printf("删除指定位置的结点\n");
 //   list_delete(head, 3);
 //   list_show_back(head);
 //   list_delete(head, 1);
 //   list_show_back(head);
 //   list_delete(head, 0);
 //   list_show_back(head);
//
 //   printf("删除指定数值结点\n");
 //   list_delete_value(head,1);
 //   list_show_back(head);
 //   list_delete_value(head,2);
 //   list_show_back(head);
 //   list_delete_value(head,3);
 //   list_show_back(head);
 //   list_delete_value(head,1);
 //   list_show_back(head);

      printf("销毁\n");
      list_free(&head);

      return 0;
}

//--------------------------函数定义--------------------------
// 创建一个空链表
plinklist list_create()
{
    plinklist head = (plinklist)malloc(sizeof(linknode));
    if (head == NULL)
    {
        printf("head malloc faild\n");
        return NULL;
    }
    head->data = 0;
    head->next = head->pre = NULL;
    return head;
}
// 获得指定位置的结点
plinklist list_get(plinklist H, int pos)// 通过pos 获得第pos个位置的结点
{
    if (H == NULL)
    {
        printf("list is error\n");
        return NULL;
    }
    if (H->next == NULL)
    {
        printf("list is error\n");
        return NULL;
    }
    if (pos < 1&&pos !=0)
    {
        printf("pos is error\n");
        return NULL;
    }
    if(pos == 0)
    {
        return H;
    }
    plinklist phead = H->next;
    int i = 1;
    while(i<pos)
    {
        phead=phead->next;
        i++;
        if(phead==NULL)
        {
            printf("pos is large\n");
            return NULL;
        }
    }
    //此时phead指向pos指定结点
    printf("结点 %d 的值为 %d\n",pos,phead->data);
    return phead;
}
// 判断是否尾空链表
int empty(plinklist H)
{
    if(H==NULL)
    {
        printf("list is error\n");
        return -1;
    }
    if(H->next==NULL)
    {
        printf("list is empty\n");
        return 1;
    }
    return 0;
}
// 头插
int list_head_insert(plinklist H, DATA_TYPE value)
{
    if (H == NULL)
    {
        printf("list is error\n");
        return -1;
    }
    // 创建新结点
    plinklist newnode = (plinklist)malloc(sizeof(linknode));
    if (newnode == NULL)
    {
        printf("newnode malloc faild\n");
        return -1;
    }
    newnode->data = value;
    newnode->next = newnode->pre = NULL;
    // 更新指针指向
    newnode->next = H->next;
    if (H->next != NULL)
    {
        H->next->pre = newnode;
    }

    newnode->pre = H;
    H->next = newnode;
    return 0;
}
// 尾插
int list_tail_insert(plinklist H, DATA_TYPE value)
{
    if(H==NULL)
    {
        printf("list is error\n");
        return -1;
    }
    plinklist phead=H;
    while(phead->next!=NULL)
    {
       phead=phead->next;
    }
    //此时phead指向尾结点
    plinklist newnode=(plinklist)malloc(sizeof(linknode));
    if(newnode==NULL)
    {
        printf("newnode malloc faild\n");
        return -1;
    }
    newnode->data=value;
    newnode->next=newnode->pre=NULL;

    //更新指针指向
    newnode->pre=phead;
    phead->next=newnode;

    return 0;
}
// 指定位置插入
int list_insert(plinklist H, DATA_TYPE value, int pos)// 将value插入到第pos结点之前
{
    if (H == NULL)
    {
        printf("list is error\n");
        return -1;
    }
    if (H->next == NULL)
    {
        printf("list is error\n");
        return -1;
    }
    if (pos < 1)
    {
        printf("pos is error\n");
        return -1;
    }
    plinklist phead;
    phead=list_get(H,pos-1);
    plinklist newnode=(plinklist)malloc(sizeof(linknode));
    newnode->data=value;
    newnode->next=newnode->pre=NULL;

    //更新指针指向 
    if(phead->next==NULL)
    {
        phead->next=newnode;
        newnode->pre=phead;
        return 0;
    }
    newnode->next=phead->next;
    phead->next->pre=newnode;
    phead->next=newnode;
    newnode->pre=phead;
    return 0;
}
// 销毁链表
int list_free(plinklist *H)
{
    if((*H)==NULL)
    {
        printf("list is error\n");
        return -1;
    }
    plinklist phead=(*H);
    while((*H))
    {
        *H=(*H)->next;
        printf("dfre data:%d\n",phead->data);
        memset(phead,0,sizeof(linknode));
        free(phead);
        phead=(*H);
    }
    return 0;
}
// 删除某一个位置上的结点
int list_delete(plinklist H, int pos)
{
    if (H == NULL)
    {
        printf("list is error\n");
        return -1;
    }
    if (H->next == NULL)
    {
        printf("list is error\n");
        return -1;
    }
    if (pos < 1)
    {
        printf("pos is error\n");
        return -1;
    }
    plinklist phead = H->next;
    int i = 1;
    while (i < pos)
    {
        phead = phead->next;
        i++;
    }
    // 此时phead指向要删除的结点
    if (phead->next == NULL)
    {
        phead->pre->next = NULL;
        return 0;
    }
    else
    {
        phead->next->pre = phead->pre;
        phead->pre->next = phead->next;
    }

    memset(phead, 0, sizeof(linknode));
    free(phead);

    return 0;
}
// 删除value值所在的结点
int list_delete_value(plinklist H, DATA_TYPE value)
{
    if (H == NULL)
    {
        printf("list is error\n");
        return -1;
    }
    if (H->next == NULL)
    {
        printf("list is error\n");
        return -1;
    }
    plinklist phead=H->next;
    while(phead!=NULL)
    {
        if(phead->data!=value)
        {
            phead=phead->next;
        }
        else
        {
            break;
        }
    }
    if(phead==NULL)
    {
        printf("not find value\n");
        return -1;
    }
    //此时phead指向要删除的结点
    if (phead->next == NULL)
    {
        phead->pre->next = NULL;
        return 0;
    }
    else
    {
        phead->next->pre = phead->pre;
        phead->pre->next = phead->next;
    }

    memset(phead, 0, sizeof(linknode));
    free(phead);

    return 0;
}
// 修改结点数据  找到原数据  修改为新数据
int list_change_vlaue(plinklist H, DATA_TYPE oldvalue, DATA_TYPE newvalue)
{
    if (H == NULL)
    {
        printf("list is error\n");
        return -1;
    }
    if (H->next == NULL)
    {
        printf("list is error\n");
        return -1;
    }
    plinklist phead=H->next;
    while(phead!=NULL)
    {
        if(phead->data!=oldvalue)
        {
            phead=phead->next;
        }
        else
        {
            break;
        }
    }
    if(phead==NULL)
    {
        printf("not find oldvalue\n");
        return -1;
    }
    //此时phead指向要修改的结点
    phead->data=newvalue;
    return 0;
    
}
// 向前遍历链表
int list_show_forward(plinklist H)
{
    if(H==NULL)
    {
        printf("list is error\n");
        return -1;
    }
    if(H->next==NULL)
    {
        printf("list is empty\n");
        return -1;
    }
    plinklist phead=H;
    //找到尾结点
    while(phead->next!=NULL)
    {
        phead=phead->next;
    }
    while (phead!=H)
    {
        printf("%d\t",phead->data);
        phead=phead->pre;
    }
    printf("\n");
    return 0;

}
// 向后遍历链表
int list_show_back(plinklist H)
{
    plinklist phead = H->next;
    if (H == NULL)
    {
        printf("list is error\n");
        return -1;
    }
    if (H->next == NULL)
    {
        printf("list is empty\n");
        return -1;
    }
    while (phead != NULL)
    {
        printf("%d\t", phead->data);
        phead = phead->next;
    }
    printf("\n");
    return 0;
}